package leetcode_300;

import java.util.ArrayList;
import java.util.List;

import helpclass.TreeNode;


/**
 *@author 周杨
 *LowestCommonAncestorOfABinaryTree_236  找两个节点的最近祖先
 *describe:用递归  每次判断自己是否是祖先 此时只有两种情况  左子树节点是两者祖先 右子树节点是两者祖先 AC 100%
 *2018年6月25日 下午6:00:52
 */
public class LowestCommonAncestorOfABinaryTree_236 {
	boolean flag=false;
	public static void main(String[] args) {
		LowestCommonAncestorOfABinaryTree_236 test=new LowestCommonAncestorOfABinaryTree_236();
		TreeNode root=new TreeNode(3);
		root.left=new TreeNode(5);
		root.right=new TreeNode(1);
		root.left.left=new TreeNode(6);
		root.left.right=new TreeNode(2);
		root.left.right.left=new TreeNode(7);
		root.left.right.right=new TreeNode(4);
		root.right.left=new TreeNode(0);
		root.right.right=new TreeNode(8);
		List<TreeNode> pathP=new ArrayList<TreeNode>();
		test.path(7,root,pathP);
		test.print(pathP);
	}

	/**
	 * describe:比较Path AC 11%
	 * 2018年6月25日 下午6:01:29
	 */
	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pathP=new ArrayList<TreeNode>();
        path(p.val,root,pathP);
        List<TreeNode> pathQ=new ArrayList<TreeNode>();
        flag=false;
        path(q.val,root,pathQ);
        int indexP=pathP.size()-1;
        int indexQ=pathQ.size()-1;
        if(indexP>indexQ) {
        	indexP=indexQ;
        }
        else if(indexP<indexQ)
        	indexQ=indexP;
        while(indexP>=0) {
        	if(pathP.get(indexP).val==pathQ.get(indexP).val)
        		return pathP.get(indexP);
        	--indexP;
        }
        return null;
        
    }
	
	public void print(List<TreeNode> res) {
		for(TreeNode now:res)
			System.out.println(now.val);
	}
	
	public void path(int val,TreeNode root,List<TreeNode> res){
			if(val==root.val) {
				res.add(root);
				flag=true;
				return ;
			}
			res.add(root);
			if(!flag) {
				if(root.left!=null)
					path(val,root.left,res);
			}
			if(!flag) {
				if(root.right!=null)
					path(val,root.right,res);
			}
			if(!flag)
			res.remove(root);
	}
	
	/**
	 * describe:递归每次都把祖先找出来 找最近的祖先
	 * 2018年6月25日 下午6:05:41
	 */
	public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {//没有找到 或者匹配到自己了
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        if (left != null && right != null) {//如果返回不为空 说明自己就是祖先
            return root;
        }
        
        return left != null ? left : right;//自己不是祖先 那一定有解在子树里
    }
}
